//
//  Problem1558.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/21.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1558. 得到目标数组的最少函数调用次数

 func modify(arr, op, i) {
    if (op == 0) {
        arr[i] ++
    }
    if (op == 1) {
        for (i = 0; i < arr.len; i++) {
            arr[i] *= 2
        }
    }
 }

 给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。
 请你返回将 arr 变成 nums 的最少函数调用次数。
 答案保证在 32 位有符号整数以内。

 示例 1：
     输入：nums = [1,5]
     输出：5
     解释：给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。
     将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。
     给两个数字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。
     总操作次数为：1 + 2 + 2 = 5 。
 示例 2：
     输入：nums = [2,2]
     输出：3
     解释：给两个数字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。
     将所有数字乘以 2 ： [1, 1] -> [2, 2] （1 次操作）。
     总操作次数为： 2 + 1 = 3 。
 示例 3：
     输入：nums = [4,2,5]
     输出：6
     解释：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5] （nums 数组）。
 示例 4：
     输入：nums = [3,2,2,4]
     输出：7
 示例 5：
     输入：nums = [2,4,8,16]
     输出：8
 提示：
     1 <= nums.length <= 10^5
     0 <= nums[i] <= 10^9
 */
@objcMembers class Problem1558: NSObject {
    func solution() {
        print(minOperations([1,5]))
    }
    
    /*
     贪心：
     思路：
     1: 数组中的奇数，肯定要执行一次第一步的操作，例如 9 = 8+1 得到的，
     2: 数组中的偶数，肯定要执行第二步的操作，减少次数，例如：8 / 2。如果是6/2=3，那么又变成奇数，还需向上面一样-1
     所以我们需要做的的是：统计数组的每个数：如果是奇数-1，偶数/2，然后继续判断奇偶，
     进阶就是：转换成二进制 5 101 需要-1的次数是2，就是1的个数，/2的次数就是二进制的长度-1
     但是我们进行/2的时候，为了减少次数：我们要整体/2，所有我们只需统计最大值/2的次数，也就是最大值的二进制的长度-1
     然后在统计每个值转换成二进制1的个数
     */
    func minOperations(_ nums: [Int]) -> Int {
        var sum = 0
        var maxValue = 0
        var n = 0
        for num in nums {
            maxValue = max(maxValue, num)
            n = num
            while n != 0 {
                if (n & 1) != 0 {   // 统计1的个数
                    sum += 1
                }
                n >>= 1
            }
        }
        
        if maxValue != 0 {
            while maxValue != 0 {
                sum += 1
                maxValue >>= 1
            }
            sum -= 1
        }
        
        return sum
    }
}
